The present invention relates to an arithmetic processor capable of high-speed arithmetic operation and to an arithmetic addition/subtraction unit therefor, and, more particularly, to a high-speed arithmetic processor which has a cellular array structure including a number of such arithmetic addition/subtraction units which may be compactly fabricated on an LSI chip.
A high speed adder, multiplier and divider are respectively discussed in Trans. of IECE Japan, No.2, 1986, pp.187; Trans. of IECE Japan, Vol.J66-D, No.6, 1983, pp.683 to 690; and Trans. of IECE Japan, Vol.J67-D, No.4, 1984, pp.450 to 457. Those arithmetic units execute multiplication or division by means of combinational circuitry using the redundant binary expression (a kind of signed digit expression) in which each digit is represented by a set of elements {-1, 0, 1}.
In particular, a prior art divider of the shift, subtract restore type uses the redundant binary expression and is implemented by ECL (emitter-coupled-logic) circuitry. While that prior art divider has faster arithmetic processing speeds than other types of conventional dividers, no consideration has been given to factors which are important for fabricating such a divider commercially, such as a reduction in the number and size of transistors and use of other types of circuitry, e.g., CMOS.
Dividers in wide use today are sequential circuits each having a subtracter (adder) and a shifter. However, it is well known that, as the number of digits of the operands increases, an exceedingly long time is required for those dividers to perform arithmetic operations. On the other hand, large-size computers having high-speed multipliers often employ multiplication-type division in which division is performed by repetition of multiplication. However, implementation of such multiplication-type division by combinational circuitry requires large numbers of hardware elements, and is therefore impractical.
With respect specifically to a high-speed arithmetic unit employing signed digit numbers for arithmetic operation, a method has been proposed in which an arithmetic operation such as multiplication or division is carried out by combinational circuitry utilizing an ECL logic element that enables NOR and OR operations to be simultaneously performed. However, exhaustive consideration has heretofore not been given to problems which must be solved to put that proposed high-speed arithmetic unit into practical use, such as reducing the number of transistors required and implementation using other types of circuitry, and, therefore, the following problems are associated with that proposed high-speed arithmetic unit:
(1) As the number of digits of the operands increases, the number of transistors required increases, which makes it difficult to fabricate an arithmetic unit capable of handling a large number of digits on a single LSI chip.
(2) When the arithmetic unit is implemented using, for example, a MOS circuit which cannot perform NOR and OR operations at the same time, the OR circuit is implemented by elements formed in two stages, that is, a NOR gate and an inverter, and the number of stages or gates required in the arithmetic circuit increases correspondingly, resulting in an increase in operation time.